package everyday;

import java.util.*;

/**
 * @author zhangmin
 * @create 2022-05-02 18:35
 * 删除无效的括号
 *  给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 *  返回所有可能的结果。答案可以按 任意顺序 返回。
 *
 *  思路：回溯
 *  先遍历字符串找到需要删除多少个左括号，多少右括号，然后通过回溯，去在不同位置删除这些多余的括号
 */
public class removeInvalidParentheses301 {
    Set<String> res=new HashSet<>();
    String str;
    //max记录最终结果中最多可以有多少的括号对，len表示删除后的字符串长度
    int max,len;
    //count遇到左括号+1，遇到由括号减一，用来保证这个path中的每一步都不会出现左括号小于右括号的不合法情况
    void backtrack(int index,int left,int right,int count,String path){
        if (left<0||right<0||count>max||count<0){
            return;
        }
        if (left==0&&right==0){
            if (path.length()==len){
                res.add(path);
            }
        }
        if (index==str.length())return;
        char c=str.charAt(index);
        if (c=='('){
            //在path中加入c，表示c没有被删除
            backtrack(index+1,left,right,count+1,path+c);
            //删除c
            backtrack(index+1,left-1,right,count,path);
        }else if (c==')'){
            backtrack(index+1,left,right,count-1,path+c);
            backtrack(index+1,left,right-1,count,path);
        }else {
            //遇到字母，直接加入
            backtrack(index+1,left,right,count,path+c);
        }
    }
    public List<String> removeInvalidParentheses(String s) {
        //先找出需要删除多少的左右括号
        str=s;
        //l，r记录需要删除多少左右括号，cl，cr记录出现了多少左右括号
        int l=0,r=0,cl=0,cr=0;
        for (char c:s.toCharArray()) {
            if (c=='('){
                cl++;
                l++;
            }else if (c==')'){
                cr++;
                if (l!=0){
                    l--;
                }else {
                    r++;
                }
            }
        }
        len=s.length()-l-r;
        max=Math.min(cr,cl);
        backtrack(0,l,r,0,"");
        return new ArrayList<>(res);
    }
}
